#pragma once

#include "znx_defs.h"

typedef struct znx_rbtree_node_s znx_rbtree_node_t;

struct znx_rbtree_node_s {
    znx_rbtree_node_t   *left;
    znx_rbtree_node_t   *right;
    znx_rbtree_node_t   *parent;
    char                color;
};

typedef struct znx_rbtree_s znx_rbtree_t;

typedef int (*znx_rbtree_node_cmp_pt) (znx_rbtree_node_t *a,
    znx_rbtree_node_t *b);

struct znx_rbtree_s {
    znx_rbtree_node_t           *root;
    znx_rbtree_node_t           *sentinel;
    znx_rbtree_node_cmp_pt      cmp;
};

#define znx_rbtree_init(tree, s, c)                         \
    znx_rbtree_sentinel_init(s);                            \
    (tree)->root = s;                                       \
    (tree)->sentinel = s;                                   \
    (tree)->cmp = c

void znx_rbtree_insert(znx_rbtree_t *tree, znx_rbtree_node_t *node);
void znx_rbtree_delete(znx_rbtree_t *tree, znx_rbtree_node_t *node);
znx_rbtree_node_t *znx_rbtree_lookup(znx_rbtree_t *tree, znx_rbtree_node_t *target);
znx_rbtree_node_t *znx_rbtree_ge(znx_rbtree_t *tree, znx_rbtree_node_t *target);
znx_rbtree_node_t *znx_rbtree_le(znx_rbtree_t *tree, znx_rbtree_node_t *target);

#define znx_rbt_red(node)               ((node)->color = 1)
#define znx_rbt_black(node)             ((node)->color = 0)
#define znx_rbt_is_red(node)            ((node)->color)
#define znx_rbt_is_black(node)          (!znx_rbt_is_red(node))
#define znx_rbt_copy_color(n1, n2)      (n1->color = n2->color)

/* a sentinel must be black */
#define znx_rbtree_sentinel_init(node)  znx_rbt_black(node)

static inline znx_bool_t
znx_rbtree_empty(znx_rbtree_t *tree) {
    return tree->root == tree->sentinel;
}

static inline znx_rbtree_node_t *
znx_rbtree_min(znx_rbtree_node_t *node, znx_rbtree_node_t *sentinel) {
    if (node == sentinel) {
        return sentinel;
    }

    while (node->left != sentinel) {
        node = node->left;
    }

    return node;
}

static inline znx_rbtree_node_t *
znx_rbtree_max(znx_rbtree_node_t *node, znx_rbtree_node_t *sentinel) {
    if (node == sentinel) {
        return sentinel;
    }

    while(node->right != sentinel) {
        node = node->right;
    }

    return node;
}

znx_rbtree_node_t *znx_rbtree_next(znx_rbtree_t *tree, znx_rbtree_node_t *node);

#define znx_rbtree_data(node, type, link)               \
    (type *) ((char *) node - offsetof(type, link))

